#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10001;
const int M = 1e7+1;

int n,m;
LL values[N],cost[N];
LL ans[M];


int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>cost[i]>>values[i];
	for(int i=1;i<=m;i++){
		for(int j=cost[i];j<=n;j++){
			ans[j]=max(ans[j],ans[j-cost[i]]+values[i]);
		};
	};
	cout<<ans[n];
	return 0;
} 
